//给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。 
//
// 返回这个矩形可能的 最小 面积。 
//
// 
//
// 示例 1： 
//
// 
// 输入： grid = [[0,1,0],[1,0,1]] 
// 
//
// 输出： 6 
//
// 解释： 
//
// 
//
// 这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。 
//
// 示例 2： 
//
// 
// 输入： grid = [[0,0],[1,0]] 
// 
//
// 输出： 1 
//
// 解释： 
//
// 
//
// 这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length, grid[i].length <= 1000 
// grid[i][j] 是 0 或 1。 
// 输入保证 grid 中至少有一个 1 。 
// 
//
// Related Topics 数组 矩阵 👍 17 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-08-22 19:45:34
 * @description 3195.包含所有 1 的最小矩形面积 I
 
 */
 
public class FindTheMinimumAreaToCoverAllOnesI {
    public static void main(String[] args) {
    //测试代码
    FindTheMinimumAreaToCoverAllOnesI fun = new FindTheMinimumAreaToCoverAllOnesI();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
给你一个二维 二进制 数组 grid。
请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，
并且满足 grid 中所有的 1 都在矩形的内部。
返回这个矩形可能的 最小 面积。
示例 1：
输入： grid = [[0,1,0],[1,0,1]]
输出： 6


需要确定四个边界，上下左右,用以包含所有的1
        * */
    public int minimumArea(int[][] grid) {
        int l=-1,r=-1,t=-1,b=-1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1){
                    l=Math.min(l==-1?j:l,j);
                    r=Math.max(r==-1?j:r,j);
                    t=Math.min(t==-1?i:t,i);
                    b=Math.max(b==-1?i:b,i);
                }
            }
        }
        return (r-l+1)*(b-t+1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
